Parallel computing architectures can be utilized to increase the efficiency of computing a multi-dimensional wavelet transform for signal data. The speed, accuracy, and efficiency of the transform calculating in such architectures may depend on factors such as how data is partitioned, the particular type of wavelets used in the transform, and the hardware utilized when performing the transform.
A common technique is to divide the input data into one-dimensional arrays. For each of those arrays, a one-dimensional wavelet transform is performed on a computation unit (e.g., a processor core or thread block) and the result is written back to memory. In further steps, the same procedure is done for the other dimensions of the data, with new geometric decompositions. This technique allows the transform to be performed in a parallel computing environment, thus providing some increase in the speed of the transform calculation. However, the technique has traditionally required calculation between each one-dimensional array during the transform calculation. This communication introduces a time latency into the calculation which may be unacceptable for many applications.
Several approaches have been developed to compute multi-dimensional wavelet transforms while minimizing the communication between computation units. However, an efficient parallelized implementation of a wavelet transform would preferably require no communication between the computation units. Thus, it would be desirable to utilize a parallelized multi-dimensional wavelet transform that allows each computation unit to perform its portion of the wavelet transform calculation independent of the other computation units.
Reducing or eliminating the communication latencies required for wavelet transforms can benefit various domains. For example, wavelet transforms may be used in Magnetic Resonance Imaging (“MRI”) reconstruction procedures. As would be understood by one skilled in the art, the clarity of MRI images is highly dependently on the motion of the item being scanned. Thus, for example, involuntary movements of a patient's heart or lungs during MRI scanning can blur the resultant image. Techniques such as compressed sensing have be introduced to reduce the time require for scanning, however these techniques have traditionally required time-intensive image processing before medical personnel can review the image. In turn, this processing delays the treatment of the patient. Therefore, it would be desirable to minimize the time required for processing a MRI image acquired using compressed sensing techniques so that the MRI image can be quickly presented to medical personnel to facilitate treatment of the patient.